package leetcode.图.拓扑排序.review;

import java.util.Arrays;

/**
 * @author ：zsy
 * @date ：Created 2021/9/25 23:46
 * @description：
 */
public class TopologicalSorting {
    public static void main(String[] args) {
        TopologicalSorting topologicalSorting = new TopologicalSorting();
        int[][] graph = {{0, 1, 1, 1, 0, 0}, {0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 1, 0}, {0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 1, 0}};
        char[] sourceSort = topologicalSorting.getSourceSort(graph, topologicalSorting.getSource(graph));
        System.out.println(Arrays.toString(sourceSort));
    }

    private char[] getSourceSort(int[][] graph, int[] source) {
        if (source == null || source.length == 0) return new char[0];
        int len = source.length;
        int index = 0;
        char[] sortNums = new char[graph[0].length];
        while (index < len) {
            // 寻找入度为0的节点
            for (int i = 0; i < source.length; i++) {
                if (source[i] == 0) {
                    sortNums[index++] = (char)('a' + i);
                    source[i] = -1;
                    // 所有以该点为出度的节点入度减一
                    for (int j = 0; j < graph[0].length; j++) {
                        if (graph[i][j] == 1) {
                            source[j] -= 1;
                        }
                    }
                    i = 0;
                }
            }
            if (index == len) break;
        }
        return sortNums;
    }

    /**
     * 根据邻接矩阵获取入度数组
     * @param graph
     * @return
     */
    private int[] getSource(int[][] graph) {
        if (graph.length == 0) return null;
        int[] source = new int[graph[0].length];
        for (int i = 0; i < graph.length; i++) {
            int count = 0;
            for (int j = 0; j < graph[0].length; j++) {
                if (graph[j][i] == 1) {
                    count++;
                }
            }
            source[i] = count;
        }
        return source;
    }
}
